#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;
int main()
{
    int V, N;
    cin >> V >> N;
    vector<int> val(N, 0);
    vector<int> w(N, 0);
    vector<int> cnt(N, 0);
    vector<int> dp(V + 1, 0);
    for (int i = 0; i < N; i++)
        cin >> w[i] >> val[i] >> cnt[i];

    //multipack
    for (int i = 0; i < N; i++)
    {
        int M = cnt[i];
        if (w[i] * M >= V)
        {
            for (int v = w[i]; v <= V; v++) // complete pack
                dp[v] = max(dp[v], dp[v - w[i]] + val[i]);
            continue;
        }
        int k = 1;
        while (k < M)
        {
            for (int v = V; v >= k * w[i]; v--) // 01 pack
                dp[v] = max(dp[v], dp[v - k * w[i]] + k * val[i]);
            M -= k;
            k *= 2;
        }
        for (int v = V; v >= M * w[i]; v--)// 01 pack
            dp[v] = max(dp[v], dp[v - M * w[i]] + M * val[i]);
    }
    cout << dp[V] << endl;
    reuturn 0;
}